/*************************************************************************************
 * Nombre del archivo: AFN.java
 * Universidad del Valle de Guatemala
 * Curso: Diseño de Lenguajes de Programación
 * @author martin
 *          Martín Guzmán 08041
 * Fecha: Marzo de 2010
 * Descripción:
*************************************************************************************/
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class AFN extends Automata_Finito{

    Arbol_Binario arbol;
    private static int num_estados=0;

    public AFN(){}

    public AFN(Arbol_Binario arbol){
        long tiempo_inicial = System.nanoTime();
        this.num_estados=0;

        //utiliza la construcción de Thompson para generar el AFN
        this.arbol=arbol;
        //copiar la tabla de símbolos que tenía el árbol...
        for(int i=0;i<arbol.lista_simbolos.size();i++){
            this.Sigma.add(this.arbol.lista_simbolos.get(i));
        }
        this.regex=this.arbol.padre.Mostrar_Nodo();

        Estado i_f[] = thompson(this.arbol.padre);
        this.q0 = i_f[0];
        this.F.add(i_f[1]);

        this.renumerar_estados();

        //this.Imprimir_Todo_AF();
        ordenar_transiciones();

        long tiempo_final = System.nanoTime();
        long tiempo = tiempo_final-tiempo_inicial;

        String linea = "\tAFN creado utilizando el algoritmo de Thompson";
        this.Imprimir_Todo_AF("AFN_Thompson_",linea,tiempo);
    }

    public void Simulacion_AFN(String cadena){

        
        long tiempo_inicial = System.nanoTime();

        LinkedList<Integer> S = cerradura_epsilon(this.q0.getNombre());
        //this.Print("cerradura-e del estado inicial: "+S.toString());
        /*
        for(int i=0;i<this.Q.size();i++){
            this.Print(this.Q.get(i).getNombre()+": "+this.Q.get(i).getLista());
        }
         */

        int a = 0;

        Character c = cadena.charAt(a);

        while(a<cadena.length()){
            a+=1;
            LinkedList<Integer> A = new LinkedList<Integer>();
            //this.Print("S:"+S.toString());
            for(int i=0;i<S.size();i++){
                LinkedList<Integer> lis = mueve("q"+S.get(i),c);
                for(int j=0;j<lis.size();j++){
                    this.agregar_a_lista(cerradura_epsilon("q"+lis.get(j)), A);
                }
                this.Sort_Set(A);
            }
            S.clear();
            //this.Print("A:"+A.toString());
            this.agregar_a_lista(A, S);
            if(a<cadena.length()){
                c = cadena.charAt(a);
            }
            
        }
        boolean aceptada=false;
        String ultimo_estado_aceptacion="";
        //this.Print("cerradura-e del estado: "+S.toString());
        for(int i=0;i<this.F.size();i++){
            for(int j=0;j<S.size();j++){
                if(this.comparar(this.F.get(i).getNombre(),"q"+S.get(j))){
                    ultimo_estado_aceptacion = this.F.get(i).getNombre();
                    aceptada=true;
                    break;
                }
            }

        }

        long tiempo_final = System.nanoTime();
        long tiempo = tiempo_final-tiempo_inicial;

        this.Print("La cadena (w): "+cadena+"");
        this.Print("\t* "+((aceptada)?"Sí ":"No ")+"fue aceptada");
        this.Print("\t* Tiempo de simulación: "+(tiempo)+"ns = "+(((double)(tiempo)/(double)100000))+"ms");
        String estados_alcanzados=S.toString();
        if(estados_alcanzados.compareToIgnoreCase("[]")!=0){
            estados_alcanzados=estados_alcanzados.replaceAll(", ", ", q");
            estados_alcanzados=estados_alcanzados.replace("[", "[q");
        }
        this.Print("\t* Estados aceptación del autómata: "+this.F);
        this.Print("\t* Estados alcanzados: "+estados_alcanzados);
        this.Print("\t* Último estado de aceptación: "+((ultimo_estado_aceptacion.length()==0)?" - ":""+ultimo_estado_aceptacion));

    }


     /***********************************************
     * Método: cerradura_epsilon
     * Uso: Retorna todos los estados a los que puede
     *      llegar con transiciones epsilon
     * @return LinkedList<Integer> con los números de los estados
    ***********************************************/
     public LinkedList<Integer> cerradura_epsilon(String estado){

        LinkedList<Integer> resultado = new LinkedList<Integer>();

        Stack pila = new Stack();
        LinkedList<Integer> T = this.Get_estados_se_puede_llegar_epsilon(estado);

        for(int i=0;i<T.size();i++){
            pila.push(T.get(i));
            resultado.add(T.get(i));
        }
        while(!pila.isEmpty()){
            Integer t = (Integer) pila.pop();

            LinkedList<Integer> temp = this.Get_estados_se_puede_llegar_epsilon("q"+t);
            for(int i=0;i<temp.size();i++){
                if(!resultado.contains(temp.get(i))){
                    resultado.add(temp.get(i));
                    pila.push(temp.get(i));
                }
            }
        }
        this.Sort_Set(resultado);
        return resultado;
    }


    /***********************************************
    * Método: thompson
    * Uso: Utiliza el algoritmo de thompon para generar
     *      un autómata. Recursivo
    * @return Estado[] contiene en retorno[0] la referencia
     *      al estado inicial y en retorno[1] al estado final.
    ***********************************************/
    public Estado[] thompson(Nodo<String> nodo){
        //se guarda en retorno[0] el estado inicial y en retorno[1] el estado final
        Estado[] retorno = new Estado[2];

        if(this.Sigma.contains(nodo.getNombre().charAt(0))){
            retorno[0] = new Estado("q"+(num_estados++));
            this.Q.add(retorno[0]);
            retorno[1] = new Estado("q"+(num_estados++));
            this.Q.add(retorno[1]);
            //crear la transición entre el estado final y el inicial
            this.delta.add(new Transicion(retorno[0],nodo.getNombre().charAt(0),retorno[1]));

            return retorno;
        }
        else if(comparar(nodo.getNombre(),"*")){
            retorno[0] = new Estado("q"+(num_estados++));
            this.Q.add(retorno[0]);

            Estado[] i_f = thompson(nodo.getHijo_izquierdo());

            retorno[1] = new Estado("q"+(num_estados++));
            this.Q.add(retorno[1]);
            
            //crear las 4 transiciones
                //entre el inicio y el final
            this.delta.add(new Transicion(retorno[0],Main.epsilon,retorno[1]));
                //entre el inicio y el primero del hijo
            this.delta.add(new Transicion(retorno[0],Main.epsilon,i_f[0]));
                //entre el ultimo del hijo y el final
            this.delta.add(new Transicion(i_f[1],Main.epsilon,retorno[1]));
                //entre el ultimo y el primero del hijo
            this.delta.add(new Transicion(i_f[1],Main.epsilon,i_f[0]));
        }
        else if(comparar(nodo.getNombre(),"|")){
            retorno[0] = new Estado("q"+(num_estados++));
            this.Q.add(retorno[0]);

            Estado[] i_f_arriba = thompson(nodo.getHijo_izquierdo());
            Estado[] i_f_abajo = thompson(nodo.getHijo_derecho());

            retorno[1] = new Estado("q"+(num_estados++));
            this.Q.add(retorno[1]);

            this.delta.add(new Transicion(retorno[0],Main.epsilon,i_f_arriba[0]));
            this.delta.add(new Transicion(i_f_arriba[1],Main.epsilon,retorno[1]));

            this.delta.add(new Transicion(retorno[0],Main.epsilon,i_f_abajo[0]));
            this.delta.add(new Transicion(i_f_abajo[1],Main.epsilon,retorno[1]));

        }
        else if(comparar(nodo.getNombre(),Main.concat+"")){
            //this.Print("entra a .");
            Estado[] i_f_izq = thompson(nodo.getHijo_izquierdo());
            Estado[] i_f_der = thompson(nodo.getHijo_derecho());

            retorno[0] = i_f_izq[0];
            retorno[1] = i_f_der[1];

            //copiar las transiciones
            copiar_transiciones(i_f_izq[1],i_f_der[0]);
        }
        
        return retorno;

    }

    /***********************************************
     * Método: copiar_transiciones
     * Uso: Copia las transiciones existentes entre un
     *      estado fuente y el estado destino
     * @return void
    ***********************************************/
    private void copiar_transiciones(Estado destino, Estado fuente) {
        this.ordenar_transiciones();

        String cadena = fuente.getNombre();

        LinkedList<Transicion> tran = new LinkedList<Transicion>();
        for(int i=0;i<this.Sigma.size();i++){
            LinkedList<Integer> temp_list = this.Buscar_transiciones(cadena, this.Sigma.get(i));
            //int num = this.Buscar_transicion(cadena, this.Sigma.get(i));
            if(temp_list.size()!=0){
                for(int j=0;j<temp_list.size();j++){
                    int num = temp_list.get(j);
                    tran.add(this.delta.get(num));
                }
            }
        }

        //ya se tienen las transiciones a copiar
        //remover las transiciones
        for(int i=0;i<tran.size();i++){
            this.delta.add(new Transicion(destino,tran.get(i).getTransicion(),tran.get(i).getHacia()));
            this.delta.remove(tran.get(i));
        }

        //remover el estado
        this.Q.remove(fuente);
        this.ordenar_estados();
    }


    /***********************************************
    * Método: Buscar_transicion
    * Uso: busca entre la lista de transiciones
    *      la transición que se desea
    * @return Integer con el índice en la
    *      lista de transiciones
    ***********************************************/
    public LinkedList<Integer> Buscar_transiciones(String Estado_fuente, Character caracter) {

        LinkedList<Integer> retorno_list = new LinkedList<Integer>();

        for(int i=0;i<this.delta.size();i++){
            if(this.comparar(this.delta.get(i).getDesde().getNombre(), Estado_fuente) && this.delta.get(i).getTransicion()==caracter){
                retorno_list.add(i);
            }
        }
        return retorno_list;
    }

     /***********************************************
     * Método: renumerar_estados
     * Uso: se renumeran los estados para que queden
     *     los nombres consecutivos.
     * @return void
    ***********************************************/
    public void renumerar_estados(){
        int i=0;
        for(i=0;i<this.Q.size();i++){
            this.Q.get(i).setNombre("q"+i);
        }
        this.num_estados = ++i;
    }

}
